'''
Created on 2013-7-1

@author: ZuoPeng
'''
# -*- coding: utf-8 -*-

def cf2pq(cf):
    if len(cf)>0:
        p=cf.pop()
        q=1
    else:
        return -1
    while len(cf)>0:
        a=cf.pop()
        tmp_p=p
        tmp_q=q
        q=p
        p=a*tmp_p+tmp_q
    return (p,q)

def Pells_equation(d):
# i do not want to read this the 2nd time
    root=int(d**0.5)
    if root==d**0.5 or d<0 or d>int(d):
        return -1
    
    denominator=1
    b=0
    
    cf=[]
    while True:
        a=int((root+b)/denominator)
        cf.append(a)
        
        pq=cf2pq(cf.copy())
        if pq[0]**2-pq[1]**2*d==1:
            return pq
        
        tmp_denominator,tmp_b=denominator,b
        b=a*tmp_denominator-tmp_b
        denominator=(d-(a*tmp_denominator-tmp_b)**2)/tmp_denominator
        
def continued_fractions(d):
    root=int(d**0.5)
    if root==d**0.5 or d<0 or d>int(d):
        return -1
    
    denominator=1
    b=0
    
    cf=[]
    while True:
        a=int((root+b)/denominator)           
#         cf.append(a)
        tmp_denominator,tmp_b=denominator,b
        b=a*tmp_denominator-tmp_b
        denominator=(d-(a*tmp_denominator-tmp_b)**2)/tmp_denominator
        if (a,b,denominator) in cf:
            return cf
        else:
            cf.append((a,b,denominator))
        
            
        
#         
# print(Pells_equation(7)[0])
# print(Pells_equation(7)[1])
    